#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;


/*
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1：

输入：nums = [1], k = 1
输出：1
示例 2：

输入：nums = [1,2], k = 4
输出：-1
示例 3：

输入：nums = [2,-1,2], k = 3
输出：3
 *
 * TODO md 不会
 * */
int shortestSubarray(vector<int> &nums, int k) {
    vector<long long> res(nums.size(), 0);
    res[0] = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        res[i] = res[i - 1] + nums[i];
    }
    res.insert(res.begin(), 0);
    int m = INT_MAX;
    for (int i = 0; i < res.size(); ++i) {
        for (int j = i; j < res.size(); ++j) {
            if (res[j] - res[i] >= k && j - i > 0)
                m = min(m, j - i);
            if (res[j] >= k)
                m = min(m, j);
        }
    }
    if (m == INT_MAX)
        m = -1;
    return m;

}


int shortestSubarray1(vector<int> &nums, int k) {
    vector<pair<int, long>> res(nums.size(), 0);
    res[0] = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        res[i].first = i;
        res[i].second = res[i - 1] + nums[i];
    }
    sort(res.begin(), res.end(), [](pair<int, long> &a, pair<int, long> &b) {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    });
    int m = INT_MAX;
    int low = 0;
    int high = nums.size() - 1;
    if (m == INT_MAX)
        m = -1;
    return m;

}

int shortestSubarray(vector<int> &nums, int k) {
    int n = nums.size();
    //获取前面的数据相加的和 他这个把第一个空出来了
    vector<long> preSumArr(n + 1);
    for (int i = 0; i < n; i++) {
        preSumArr[i + 1] = preSumArr[i] + nums[i];
    }


    int res = n + 1;//定义最大值
    deque<int> qu;//递增的双端队列
    for (int i = 0; i <= n; i++) {
        long curSum = preSumArr[i];//获取当前元素
        //如果队列不空 且 当前的减去队列------|元素大于等于k
        while (!qu.empty() && curSum - preSumArr[qu.front()] >= k) {
            res = min(res, i - qu.front());//获取最小下标
            qu.pop_front();//pop
        }
        //如果不空,队列后面的 值大于当前的值 就需要把队列后面的值弹出因为 cursum肯定比那个值
        //优秀
        while (!qu.empty() && preSumArr[qu.back()] >= curSum) {
            qu.pop_back();
        }

        qu.push_back(i);

    }
    // 例如 前面相加  1 3 5 6 3 比如大于等于2 就可以
    // 3 是当下值 要求他的话 咱们先和1 比 然后更新一下值
    // 然后咱们再跟6 比 发现啊 他index比咱们小但是数据比咱们大 因此呢 如果后面来值的话
    //如果6满足条件那么3也一定满足条件所以啊 咱们直接把 6弹出就行了
    return res < n + 1 ? res : -1;
}